#pragma once
#include <vector>
#include <iostream>
using namespace std;

namespace ouyang
{ 
	template<class T>
	struct less
	{	
		bool operator()(const T& left, const T& right)
		{
			return left < right;
		}
	};

	template<class T>
	struct greater
	{
		bool operator()(const T& left, const T& right)
		{
			return left > right;
		}
	};

	template<class T, class Container = vector<T>, class Compar = less<T>>
	class Priority_queue
	{
	public:
		Priority_queue()
			:_c()
		{}

		template<class Iterator>
		Priority_queue(Iterator first, Iterator end)
			: _c(first, end)
		{
			int n = _c.size();
			int parent = (n - 2) >> 1;
			for (; parent >= 0; parent--)
				AdjustDown(parent);
		}

		void push(const T& val)
		{
			_c.push_back(val);
			AdjustUp(_c.size() - 1);
		}

		void pop()
		{
			if (empty())
				return;
			swap(_c.front(), _c.back());
			_c.pop_back();
			AdjustDown(0);
		}

		size_t size() const
		{
			return _c.size();
		}

		bool empty() const
		{
			return _c.empty();
		}

		const T& top() const
		{
			return _c.front();
		}
	private:
		void AdjustUp(int child)
		{
			int parent = (child - 1) >> 1;
			while (child)
			{
				if (Compar()(_c[parent], _c[child]))
				{
					swap(_c[parent], _c[child]);
					child = parent;
					parent = (child - 1) >> 1;
				}
				else {
					break;
				}
			}
		}

		void AdjustDown(int parent)
		{
			size_t child = parent * 2 + 1;
			while (child < _c.size())
			{
				if (child + 1 < _c.size() && Compar()(_c[child], _c[child + 1]))
				{
					child += 1;
				}
				if (Compar()(_c[parent], _c[child]))
				{
					swap(_c[parent], _c[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else {
					break;
				}
			}
		}

		Container _c;
	};
}